package alo.p18;

/**
 * @ClassName MaxSumRec
 * @Description 最大连续子序列之和
 * @Author Fanxc
 * @DATE 2021/3/14 15:55
 * @Version 1.0
 */
public class MaxSumRec {
    int maxSumRec(int[] A,int left,int right){
        int MaxLeftBorderSum=0;
        int MaxRightBorderSum=0;
        int LeftBorderSum=0;
        int RightBorderSum=0;
        int mid=left+(right-left)/2;
        if (left==right){
            return Math.max(A[left], 0);
        }
        int MaxLeftSum=maxSumRec(A,left,mid);
        int MaxRightSum=maxSumRec(A,mid+1,right);
        for (int i=mid;i>=left;i--){
            LeftBorderSum+=A[i];
            if (LeftBorderSum>MaxLeftBorderSum){
                MaxLeftBorderSum=LeftBorderSum;
            }
        }
        for (int i=mid+1;i<=right;i++){
            RightBorderSum+=A[i];
            if (RightBorderSum>MaxRightBorderSum){
                MaxRightBorderSum=RightBorderSum;
            }
        }
        return Math.max(Math.max(MaxLeftSum,MaxRightSum),MaxLeftBorderSum+MaxLeftBorderSum);
    }
}
